﻿/** \file
* \$Rev: 4 $
* 
* \$Date: 2010-06-23 05:49:03 +0000 (Wed, 23 Jun 2010) $
*
* \$URL: http://fofbrainz.googlecode.com/svn/trunk/Levenshtein.cs $
*/

using System;

namespace FofBrainz
{
	using System;

	/// <summary>
	/// Contains approximate string matching.
	/// Based on http://dotnetperls.com/levenshtein
	/// </summary>
	static class LevenshteinDistance
	{
		/// <summary>Compute the distance between two strings.</summary>
		/// <param name="s">The first string to compare.</param>
		/// <param name="t">The second string to compare.</param>
		/// <returns>The Levenshtein distance between s and t.</returns>
		public static int Compute(string s, string t)
		{
			int n = s.Length;
			int m = t.Length;
			int[,] d = new int[n + 1, m + 1];

			if (n == 0)
				return m;

			if (m == 0)
				return n;

			for (int i = 0; i <= n; i++)
				d[i, 0] = i;

			for (int j = 0; j <= m; j++)
				d[0, j] = j;

			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j <= m; j++)
				{
					int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

					d[i, j] = Math.Min(
						Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
						d[i - 1, j - 1] + cost);
				}
			}
			return d[n, m];
		}
	}
}
